package Lee_code;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author blh
 * 用最少数量的箭引爆气球
 * @date 2024年11月01日 8:53
 */
public class Lee_452_111 {
    public int findMinArrowShots(int[][] points) {
        int n = points.length;
        int[] dp = new int[n];
        dp[0] = 1;
        Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));

        for (int i = 1; i < n; i++) {
            // 更新dp数组
            int left = points[i][0];
            int right = points[i][1];
            int num = 0;

            for (int j = i - 1; j >= 0; j--) {
                int tempLeft = points[j][0];
                int tempRight = points[j][1];
                left = Math.max(tempLeft, left);
                right = Math.min(tempRight, right);
                if (right <= left) {
                    // 没有重叠区间了
                    break;
                }
                num++;
            }
            dp[i] = Math.min(dp[i - 1] + 1, dp[i - 1 - num] + 1);
        }
        return dp[n - 1];
    }
}
